/**
 * 
 */
package util;

import java.util.ArrayList;

/**
 * @author alissonslp
 *
 */
public class Dijkstra {

	/**
	 * 
	 * @param G
	 * @param s
	 * @return
	 */
	public static int[] dijkstra(WeightedGraph G, int s) {
        final int[] dist = new int[G.size()];  // shortest known distance from "s"
        final int[] pred = new int[G.size()];  // preceeding node in path
        final boolean[] visited = new boolean[G.size()]; // all false initially

        for (int i = 0; i < dist.length; i++) {
            pred[i] = -1;
            dist[i] = Integer.MAX_VALUE;
        }
        dist[s] = 0;

        for (int i = 0; i < dist.length; i++) {
            final int next = minVertex(dist, visited);

            if (next >= 0) {
                visited[next] = true;

                // The shortest path to next is dist[next] and via pred[next].

                final int[] n = G.neighbors(next);
                for (int j = 0; j < n.length; j++) {
                    final int v = n[j];
                    final int d = dist[next] + G.getWeight(next, v);
                    if (dist[v] > d) {
                        dist[v] = d;
                        pred[v] = next;
                    }
                }
            }
        }
        return pred;  // (ignore pred[s]==0!)
    }
	public static int[] dijkstraF(WeightedGraph G, int s) {
		final int[] dist = new int[G.size()];  // shortest known distance from "s"
        final int[] pred = new int[G.size()];  // preceeding node in path
        final boolean[] visited = new boolean[G.size()]; // all false initially

        for (int i = 0; i < dist.length; i++) {
            pred[i] = -1;
            dist[i] = Integer.MAX_VALUE;
        }
        dist[s] = 0;

        for (int i = 0; i < dist.length; i++) {
            final int next = minVertex(dist, visited);

            if (next >= 0) {
                visited[next] = true;

                // The shortest path to next is dist[next] and via pred[next].

                final int[] n = G.neighbors(next);
                for (int j = 0; j < n.length; j++) {
                    final int v = n[j];
                    final int d = dist[next] + (-1)*G.getWeight(next, v);
                    if (dist[v] > d) {
                        dist[v] = d;
                        pred[v] = next;
                    }
                }
            }
        }
        return pred;  // (ignore pred[s]==0!)
    }
	
	/**
	 * 
	 * @param G
	 * @param s
	 * @return
	 */
	public static int[] dijkstraHop(WeightedGraph G, int s) {
        final int[] dist = new int[G.size()];  // shortest known distance from "s"
        final int[] pred = new int[G.size()];  // preceeding node in path
        final boolean[] visited = new boolean[G.size()]; // all false initially

        for (int i = 0; i < dist.length; i++) {
            pred[i] = -1;
            dist[i] = Integer.MAX_VALUE;
        }
        dist[s] = 0;

        for (int i = 0; i < dist.length; i++) {
            final int next = minVertex(dist, visited);

            if (next >= 0) {
                visited[next] = true;

                // The shortest path to next is dist[next] and via pred[next].

                final int[] n = G.neighbors(next);
                for (int j = 0; j < n.length; j++) {
                    final int v = n[j];
                    final int d = dist[next] + 1;
                    if (dist[v] > d) {
                        dist[v] = d;
                        pred[v] = next;
                    }
                }
            }
        }
        return pred;  // (ignore pred[s]==0!)
    }
	
	/**
	 * 
	 * @param G
	 * @param src
	 * @param dst
	 * @return
	 */
	public static int[] getShortestPath(WeightedGraph G, int src, int dst) {
        int x;
        int[] sp;
        ArrayList<Integer> path = new ArrayList<Integer>();

//        System.out.println(G.toString());
        final int[] pred = dijkstra(G, src);

        x = dst;
        int cont = 0;
        while (x != src) {
        	if(cont>G.size()) {
        		return null;
        	}
            path.add(0, x);
            x = pred[x];
            // No path
            if (x == -1) {
                return new int[0];
            }
            cont++;
        }
        path.add(0, src);
        sp = new int[path.size()];
        for (int i = 0; i < path.size(); i++) {
            sp[i] = path.get(i);
        }
        return sp;
    }
	public static int[] getShortestPathF(WeightedGraph G, int src, int dst) {
		int x;
        int[] sp;
        ArrayList<Integer> path = new ArrayList<Integer>();

//        System.out.println(G.toString());
        final int[] pred = dijkstra(G, src);

        x = dst;

        while (x != src) {
            path.add(0, x);
            x = pred[x];
            // No path
            if (x == -1) {
                return new int[0];
            }
        }
        path.add(0, src);
        sp = new int[path.size()];
        for (int i = 0; i < path.size(); i++) {
            sp[i] = path.get(i);
        }
        return sp;
    }
	
	/**
	 * 
	 * @param G
	 * @param src
	 * @param dst
	 * @return
	 */
	public static int[] getShortestHopPath(WeightedGraph G, int src, int dst) {
        int x;
        int[] sp;
        ArrayList<Integer> path = new ArrayList<Integer>();

//        System.out.println(G.toString());
        final int[] pred = dijkstraHop(G, src);

        x = dst;
        int cont = 0;
        while (x != src) {
        	if(cont>G.size()) {
        		return null;
        	}
            path.add(0, x);
            x = pred[x];
            // No path
            if (x == -1) {
                return new int[0];
            }
            cont++;
        }
        path.add(0, src);
        sp = new int[path.size()];
        for (int i = 0; i < path.size(); i++) {
            sp[i] = path.get(i);
        }
        return sp;
    }

	/**
	 * 
	 * @param dist
	 * @param v
	 * @return
	 */
	private static int minVertex(int[] dist, boolean[] v) {
        int x = Integer.MAX_VALUE;
        int y = -1;   // graph not connected, or no unvisited vertices
        for (int i = 0; i < dist.length; i++) {
            if (!v[i] && dist[i] < x) {
                y = i;
                x = dist[i];
            }
        }
        return y;
        
    }
	
	/**
	 * @param graph
	 * @param id
	 * @param id2
	 */
	public static int getShortestCost(WeightedGraph graph, int src, int dst) {
		final int[] dist = new int[graph.size()];  // shortest known distance from "s"
        final int[] pred = new int[graph.size()];  // preceeding node in path
        final boolean[] visited = new boolean[graph.size()]; // all false initially

        for (int i = 0; i < dist.length; i++) {
            pred[i] = -1;
            dist[i] = Integer.MAX_VALUE;
        }
        dist[src] = 0;

        for (int i = 0; i < dist.length; i++) {
            final int next = minVertex(dist, visited);

            if (next >= 0) {
                visited[next] = true;

                // The shortest path to next is dist[next] and via pred[next].

                final int[] n = graph.neighbors(next);
                for (int j = 0; j < n.length; j++) {
                    final int v = n[j];
                    final long d = (long)dist[next] + (long)graph.getWeight(next, v);
                    if (dist[v] > d) {
                        dist[v] = (int)d;
                    }
                }
            }
        }
        return dist[dst];  // (ignore pred[s]==0!)
	}
}
